# -*- coding: UTF-8 -*-
from typing import List
from leetcode_helper import TestcaseHelper, SolutionBase


class Solution(SolutionBase):
    # 解题的方法，命名和Leetcode的保持一致即可
    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
        def val(ch) -> int:
            return ord(ch) - ord('a') + 1

        s_len = len(s)
        pos = -1
        sub_str = s[s_len - k: s_len]
        hash_value = 0
        multi_power = 1

        '''
        用pow来求几次幂，在字符串很长时会很耗时O(n^2)
        '''
        for i in range(k):
            if i != 0:
                multi_power *= power
            hash_value += val(sub_str[i]) * multi_power

        mod_value = hash_value % modulo

        if mod_value == hashValue:
            pos = s_len - k

        for i in range(s_len - k - 1, -1, -1):
            hash_value = (hash_value - val(s[i+k]) * multi_power) * power + val(s[i])
            mod_value = hash_value % modulo
            if mod_value == hashValue:
                pos = i

        return s[pos: pos + k]


if __name__ == '__main__':
    # 按照leetcode的题目说明，将基本的test case填入
    # 每条case的最后一个元素是正确的结果，即期待的结果
    # 使用元组来保存输入的数据，期待的结果
    testcases = [
        ("fbxzaad", 31, 100, 3, 32, "fbx"),
        ("bzzrtrrpppigevriaooetwawtnfwddgdvoldxucsbyaufhygdxpnxupmvwbryzlgiuierypzqvwiywqlwiygyj",
         76, 4, 60, 2, "bzzrtrrpppigevriaooetwawtnfwddgdvoldxucsbyaufhygdxpnxupmvwbr"),
        ("leetcode", 7, 20, 2, 0, "ee")
    ]

    for case_item in testcases:
        solution = Solution()
        input1 = case_item[0]
        input2 = case_item[1]
        input3 = case_item[2]
        input4 = case_item[3]
        input5 = case_item[4]
        expect = case_item[len(case_item) - 1]
        # TODO: 调用对应方法，需要替换具体的方法
        exec_result = solution.subStrHash(input1, input2, input3, input4, input5)

        # 判断执行结果，输出提示信息
        check_result = solution.check_result(expect, exec_result)
        TestcaseHelper.print_case(check_result, case_item, exec_result)
